package leetcode_动态规划._05最长递增子序列;

import java.util.Arrays;

/**
 * 最长数对链
 */
public class _646 {

    public int findLongestChain(int[][] pairs) {
        int ans = 1;
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        for (int i = 1; i < pairs.length; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0] && dp[i] <= dp[j]) {
                    ++dp[i];
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
